A database carries a great number of numeric data stored therein as the search target, and processing such as searching, extraction, and the like of the numeric data is performed in a database system in response to the requests made by users.
For example, in a database which stores and manages company-secret numeric data, the numeric data stored in the database is encrypted in order to suppress leakage and the like of the data to the third parties other than the legitimate users. In a case where each numeric data as the structural elements of the database is encrypted, it is possible to conceal the original numeric data itself from the third parties to some extent.
However, for example, when a cipher-text I in which numeric data is encrypted is compared with another encrypted cipher-text II, it is possible to assess the greater-than-and-less-than relation regarding the original numerical data which correspond to the cipher-texts I and II, respectively, through comparing the character strings contained in the both cipher-texts.
Further, through repeatedly executing the comparison processing of the greater-than-and-less-than relation by using various comparison target data, the numeric data itself corresponding to the cipher-text can be specified even by a user that does not have any knowledge regarding the key used for the encryption.
Specifically, in a case where it is required from a user to extract a tuple of greater (or smaller) numerical value than a given value having a specific property in operating a database system having table information (table) that is a set of tuples having various properties, it is possible for the database system side to assess the greater-than-and-less-than relation of the encrypted numerical values without knowing the key used for the encryption. Therefore, it is possible to respond to the request from the user.
Further, when it is possible to know the consistency regarding a specific number of character strings in the prefixes contained in the target cipher-text and another cipher-text in the tuples in which the numerical values are encrypted, the greater-than-and-less-than relation of the cipher-texts may not be assessed directly in some cases.
In such case, all the cipher-texts of the tuples to be the candidates for the consistent character strings of the prefixes contained in the cipher-texts need to be extracted from the table information, so that a desired numeric data cannot be extracted surely.
Further, the orders of the data are saved before and after the encryption in in the table information of the database, so that the greater-than-and-less-than relation of the numerical values of the plain texts may be conjectured from the cipher-texts.
As a known related technique for that, a method which encrypts numeric data stored in a database is known (Non-Patent Document 1). With the known related technique, when a given numerical value M as a plain text and a key K are given, a cipher-text C is generated as C=ENC (K, M) by using a given encryption function ENC.
Further, in this case, regarding two numbers M and M′ (defined as arbitrary M>M′), ENC (K, M)>ENC (K, M′) applies.
That is, when C=ENC (K, M) and C′=ENC (K, M′) are given, it is possible to assess the greater-than-and-less-than relation of M and M′ without decrypting C and C′.
Further, as a method for comparing the extent of the encrypted numerical values, there is known a method disclosed in Non-Patent Document 2.
The method disclosed in Non-Patent Document 2 is a kind of common key encryption with which: a document M (100) as a plain text expressed by being divided into a plurality of blocks as in M=(b[1], - - - ,b[N]) is encrypted to generate a cipher-text 101 that is constituted with a plurality of blocks as in C=(C[1], C[2], - - - ,C[n]). The content thereof is disclosed in FIG. 8 to FIG. 9.
In that case, when the first k-pieces in the two plain texts to be compared are the same, the first k-blocks of the cipher-texts thereof are also equivalent. Thus, partial consistency can be assessed while being remained in the state of cipher-texts. Therefore, when the first k-blocks are consistent in two plain texts regarding given k, it means that there are consistent prefixes therein or k-pieces of prefixes are consistent.
Further, referring to FIG. 8, when a key K105 as well as the document M 100 as a plain text is given as M=(b[1], - - - ,b[N]), an encryption formula for generating a cipher-text C is disclosed in Non-Patent Document 2. Note here that it is defined as C[0]=0.
Further, this related technique selects b[i] regarding i=1, 2, - - - ,N, uses the key K105 along with (i−1)-th block 107 of the cipher-text and recursively uses a deriving device 104 achieved by a hash function or the like to calculate the i-th block C[i] 106 of the cipher-text by using the hash function (Hash).
Here, it is defined as C[i]=Hash (K, (C[i−1], b[i])).
Further, the cipher-text C101 is defined as C=(C[1], - - - ,C[N]).
Further, when the first k-pieces of blocks of the cipher-text C are named as the prefix k blocks of C and expressed as C[k], it can be expressed as C[k]=(C[1], - - - ,C[k]).
Here, the orders of the cipher-texts are compared by using the encryption method.
Particularly, when it is desired to select all cipher-texts of smaller number than a given numerical value “a” without performing decryption from a set of a plurality of numbers of cipher-texts, a set of all the prefix k-blocks C[k] of the cipher-texts C in which the number smaller than “a” and the k-pieces of prefixes are consistent regarding a given k but the k-pieces of prefixes are not consistent with the number larger than “a” is defined as P(a).
Then, regarding the size of the set, when the party that holds the smaller number of key than “a” generates P(a) and gives it to the party that holds the set of the plurality of cipher-texts, the latter can select the smaller number of cipher-texts than “a” from the held set of cipher-texts without decrypting the cipher-texts.
Non-Patent Document 1: Alexandra Boldyreva, Nathan Chenette, Younho Lee, Adam O'Neill: Order-Preserving Symmetric Encryption, EUROCRYPT 2009: 224-241
Non-Patent Document 2: Georgios Amanatidis, Alexandra Boldyreva, Adam O'Neill: Provably-Secure Schemes for Basic Query Support in Outsourced Databases. DBSec 2007: 14-30
However, even when there is no request for the numeric data from a legitimate user, it is possible with the related technique disclosed in Non-Patent Document 1 described above to perform a greater-than-and-less-than comparison of the plain-text data without decoding the encrypted data.
Therefore, even when the numeric data in the database is properly encrypted, unlawful search processing for the numerical data may be performed and a specific numeric data in the database may be acquired. Thereby, the numeric data in the database may be leaked out.
Further, with Non-Patent Document 2 described above, it is possible to compare the cipher-texts without holding the key used for the encryption (i.e., without knowing the key for the encryption) based on the consistency between the prefixes of different cipher-texts. Thus, when it is used for the database, the numeric data having the consistent character strings of the prefixes may be leaked from the database.
It is therefore an object of the present invention to improve the inconveniences of the related techniques and to provide an encryption device, a cipher-text comparison system, a cipher-text comparison method, and a cipher-text comparison program capable of performing a greater-than-and-less-than assessment of the original numerical data while keeping the concealed property of the encrypted numeric data.